package wheel.arithmetic;

import cn.hutool.core.util.ArrayUtil;
import cn.hutool.core.util.RandomUtil;
import wheel.dataStruct.impl.BinaryHeap;

/**
 * 选择排序-简单选择排序
 *
 * 从未排序的数组中找到最小的值，放到数组第一位，再从未排序的数组中找到最小的值，放到数组第二位中，循环往复下去直到世界的尽头。
 * 空间复杂度O（1）， 时间复杂度 O(N²),
 * 虽然算法很耗时间， 但比较稳定， 哦， 指的是每次的执行时间稳定， 不因为数组数据的质量（数组本身的顺序比较好）而浮动。
 */
public class SimpleSelectSort {
    public static void main(String[] args) {

        Integer[] arr = new Integer[1000000];
        for(int i=0; i<arr.length; i++){
            arr[i] = RandomUtil.randomInt(0, arr.length);
        }

//        arr = new Integer[]{10, 9, 8, 7, 6, 5, 4, 3};


//        System.out.println("输入: "+ ArrayUtil.toString(arr));


        long startTime = System.currentTimeMillis();
//        arr = execute(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("耗时: "+(endTime-startTime)+"ms");

//        System.out.println("输出: "+ ArrayUtil.toString(arr));

    }

    public static Long[] execute(Long[] arr){
        exeucte(arr, 0, arr.length);
        return arr;
    }



    public static void exeucte(Long[] arr, int startIndex, int endIndex){
        for(int i=startIndex; i<endIndex; i++){

            int minValueIndex = i;
            Long minValue = arr[minValueIndex];
            for(int j=i+1; j<=endIndex; j++){
                Long currValue = arr[j];
                if(currValue<minValue){    //如果是<=, 算法的稳定性就不成立了。
                    minValue = currValue;
                    minValueIndex = j;
                }
            }

            arr[minValueIndex] = arr[i];
            arr[i] = minValue;
        }
    }

    //耗时: 121ms 126ms 109ms 一万个
    //耗时: 9960ms 10586ms 10137ms 十万个
    //耗时: 42775ms 46032ms 47744ms 二十万个
    //一百万个 好久，没等到它完成。
    //感觉执行的时间上也不是特别稳定啊，二十万级上42.7s~47.7s，差了整整5s。
}
